package niuke;

/**
 * description:
 * author:zt
 * date:2021-08-13
 */

import java.util.Stack;

/**
 * 给定一个长度为 nn 的可能含有重复值的数组 arr ，找到每一个 ii 位置左边和右边离 ii 位置最近且值比 arr_i小的位置。
 *
 * 请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 LL 和 RR，如果不存在，则值为 -1，下标从 0 开始。
 */
public class NC157 {
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int n = nums.length;
        int[][] ans = new int[n][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()]>=nums[i]) stack.pop();
            if (stack.isEmpty()) ans[i][0] = -1;
            else ans[i][0] = stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()]>=nums[i]) stack.pop();
            if (stack.isEmpty()) ans[i][1] = -1;
            else ans[i][1] = stack.peek();
            stack.push(i);
        }
        return ans;
    }
}
